package com.kevin.Code.Backtrack;

import com.kevin.Code.LinkNode.ListNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author Vinlee Xiao
 * @Classname Subsetsii
 * @Description Leetcode 90. 子集 II 中等难度
 * @Date 2021/10/31 17:29
 * @Version 1.0
 */
public class Subsetsii {

    List<List<Integer>> result = new ArrayList<>();

    /**
     * 回溯算法
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> subsetsWithDup(int[] nums) {

        Arrays.sort(nums);
        List<Integer> combine = new ArrayList<>();
        int len = nums.length;
        result.add(new ArrayList<>());

        if (len == 0) {
            return result;
        }

        dfs(nums, combine, 0);

        return result;
    }

    /**
     * @param nums
     */
    private void dfs(int[] nums, List<Integer> combine, int startIndex) {

        //结束遍历的条件
        if (startIndex >= nums.length) {
            return;
        }


        for (int i = startIndex; i < nums.length; i++) {

            if (i > startIndex && nums[i] == nums[i - 1]) {
                continue;
            }

            combine.add(nums[i]);
            result.add(new ArrayList<>(combine));
            dfs(nums, combine, i + 1);
            combine.remove(combine.size() - 1);

        }
    }

    public static void main(String[] args) {

        Subsetsii subsetsii = new Subsetsii();
        int[] nums = new int[]{0};
        subsetsii.subsetsWithDup(nums);
        List<List<Integer>> result = subsetsii.result;

        for (List<Integer> list : result) {
            for (Integer e : list) {
                System.out.print(e + " ");
            }
            System.out.println();
        }

    }
}
